// bzoj3524
// 题意：
// 给定n(<=500000)个数ai(1<=ai<=n), 有m(<=500000)个询问，
// 每次询问一个区间[l, r]，你要输出这个区间的出现次数大于(r - l + 1)/2的
// 众数，如果没有输出0。
//
// 题解：
// 离线做法都超时了。这题是简化版的区间众数，可以用无修改可持久化线段树来做，
// 对于每个[0, i]的区间，建立一个线段树，因为题目保证每个数都是1到n的，
// 所以不需要离散化。然后每个线段树就维护出对应区间ai的个数，但是空间
// 爆炸，所以可持久化就行。
//
// run: $exec < input
#include <cstdio>

int const maxn = 500007;
int n, m;

// persistent segment tree
namespace pst
{
	int alloc = 0;
	int const tree_size = maxn * 25;
	int size[tree_size], left[tree_size], right[tree_size];
	int root[maxn];

	void insert(int l, int r, int prev, int& now, int v)
	{
		now = ++alloc;
		size[now] = size[prev] + 1;
		if (l == r) return;
		left[now] = left[prev];
		right[now] = right[prev];
		int mid = (l + r) / 2;
		if (v <= mid) insert(l, mid, left[prev], left[now], v);
		else insert(mid + 1, r, right[prev], right[now], v);
	}

	int query(int l, int r, int tl, int tr, int v)
	{
		if (l == r) return l;
		int mid = (l + r) / 2;
		if (size[left[tr]] - size[left[tl]] > v)
			return query(l, mid, left[tl], left[tr], v);
		if (size[right[tr]] - size[right[tl]] > v)
			return query(mid + 1, r, right[tl], right[tr], v);
		return 0;
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1, x; i <= n; i++) {
		scanf("%d", &x);
		pst::insert(1, n, pst::root[i - 1], pst::root[i], x);
	}
	for (int i = 0, x, y; i < m; i++) {
		scanf("%d%d", &x, &y);
		printf("%d\n", pst::query(1, n, pst::root[x - 1], pst::root[y], (y - x + 1) / 2));
	}
}

